package heap;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 题目 ：出现频率最高的k个数字
 * 题目详述：
 * 给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元素。
 * 可以按 任意顺序 返回答案。
 */
public class TopKFrequent {
    /**
     * 核心思想 ：
     * （1）使用哈希表，来统计数组中所出现的数字和数组中各个数字出现的频率；
     * （2）初始化大小为k的最小堆；（最小堆的堆顶元素，为当前数组中出现频率最高的k个数字中的最小值）
     * （3）遍历整个哈希表，
     * a.若是最小堆未满的话，即可以将当前正在遍历的entry插入到最小堆中；
     * b.若是最小堆已满的话，即需要判断当前正在遍历的entry与最小堆堆顶元素所存储的entry，
     *   其所entry中value（即，数组中数字的出现频率）的大小，
     *   若是正在遍历的entry中的value > 最小堆堆顶元素所存储的entry的value，则将最小堆的堆顶元素进行删除，同时将正在遍历的entry加入到最小堆中；
     * （4）最后，遍历完哈希表后，最小堆中所存储的元素是数组中出现频率最高的k个元素，
     *     遍历整个最小堆，将最小堆中的元素加入到int数组中去
     */
    public int[] topKFrequent(int[] nums, int k) {
        // 定义一个size变量，来保存最小堆的最大容量
        int size = k;
        // 哈希表的初始化；
        HashMap<Integer , Integer> map = new HashMap<>();
        // 最小堆的初始化
        PriorityQueue<Map.Entry<Integer , Integer>> minHeap = new PriorityQueue<>(
                // 在所创建的堆中，自定义默认的比较规则
                // 即，堆中元素的比较规则是根据entry之间的value（数组中元素出现频率）从小到大排序，
                // 即，所创建的堆类型为最小堆（所创建的堆中堆顶元素为堆中的最小元素）
                (e1, e2) -> e1.getValue() - e2.getValue()
        );

        for (int num : nums) {
            // 即，遍历整个数组，将所遍历到的元素加入到哈希表中，
            // 若是哈希表中已经存在此键值对的话，则在该元素的键值对基础上对value进行加一操作
            map.put(num , map.getOrDefault(num , 0) + 1);
        }

        // 对于哈希表中键值对的映射关系Entry进行遍历，获取map集合中所有键值对的映射关系集合
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            // 若是最小堆的当前容量还未到达最小堆的最大容量的话，即直接向最小堆中加入hashmap中当前正在遍历键值对的映射关系
            if(minHeap.size() < size){
                minHeap.offer(entry);
            }
            // 若是最小堆已满的话，有且仅有在正在遍历的键值对的映射关系中的value > 最小堆中对堆顶元素的value时，
            // 会去将最小堆中的堆顶元素进行替换成当前正在遍历的键值对的映射关系
            else if(entry.getValue() > minHeap.peek().getValue()){
                minHeap.poll();
                minHeap.offer(entry);
            }
        }

        // 定义一个int数组（大小为最小堆最大容量），用于保存堆中元素的key，同时作为返回值进行返回
        int[] result = new int[size];
        int i = 0;
        // 遍历最小堆中所有元素，来获取其中的value
        // 注意 ：此时最小堆中，所存储的元素是数组中出现频率最高的k个元素键值对的映射关系；
        // 即，由于所需要的结果为int数组，需要将最小堆中entry的key，存储到先前创建的int数组中；
        for (Map.Entry<Integer, Integer> entry : minHeap) {
            result[i] = entry.getKey();
            i++;
        }
        return result;
    }
    /**
     * 分析 ：
     * （1）空间复杂度：需要O（n）的哈希表，同时需要O（k）的最小堆，同时需要O（k）的数组，总的来说，所需要的总空间复杂度：O（n）;
     * （2）时间复杂度：遍历整个哈希表的时间复杂度为O（n），同时在堆中进行元素的新增，删除操作，所需要的时间复杂度为O（logk），总的来说，时间复杂度为O（nlogk）；
     */
}
